⟸ pàgina anterior ⟸

Exercici 11 (Tasca 2).

(regular languages, union, finite set)

Els llenguatges finits són regulars

1. Demostreu que per a tot mot w, el llenguatge \{w\} és regular.

2. Demostreu que tot llenguatge finit, és a dir, tot llenguatge consistent en un nombre finit de mots, és regular.

3. Un llenguatge L és co-finit si el seu complement \overline L és finit. Demostreu que si un llenguatge és cofinit, llavors és regular.

4. Mostreu que el llenguatge L=\{0^n \mid \text{l’expansió decimal de $\pi$ conté $n$ zeros consecutius}\} és regular.

   Ajut

   No cal conèixer cap propietat de l’expansió decimal de \pi (a banda del fet de ser infinita). Penseu en canvi en una demostració per casos no constructiva.

5. Una part crucial de la definició dels DFAs és que només poden tenir un nombre finit d’estats. Demostreu que la definició esdevindria trivial si els DFAs poguessin tenir un nombre infinit d’estats, en el sentit que tot llenguatge (diguem que sobre l’alfabet \{a,b\}) es podria reconèixer amb un DFA si li permetéssim tenir un nombre infinit d’estats.